package experiment4.knapsack;

import java.util.ArrayList;


public class BacktrackKnapsack {
    boolean[] vec;
    boolean[] resultVec;
    int capacity;
    int currentValue;
    int bestValue;
    private ArrayList<Goods> goodsArrayList;

    public boolean[] solutionVector() {
        return resultVec;
    }

    public int solution(ArrayList<Goods> goodsArrayList, int capacity) {

        this.goodsArrayList = new ArrayList<>();
        for (int i = 0;i < goodsArrayList.size();i++){
            this.goodsArrayList.add(goodsArrayList.get(i));
        }
        this.capacity = capacity;
        this.currentValue = 0;
        this.bestValue = 0;
        this.vec = new boolean[goodsArrayList.size()];
        this.resultVec = new boolean[vec.length];
        searchSolution(0);
        return bestValue;
    }



    private void searchSolution(int i) {
        if (i >= goodsArrayList.size()) {
            if (currentValue > bestValue){
                for (int j =0;j < vec.length;j++){
                    resultVec[j] = vec[j];
                }
                bestValue = currentValue;
            }

            return;
        }
        Goods goods = goodsArrayList.get(i);

        if (capacity >= goods.weight) {
            capacity -= goods.weight;
            currentValue += goods.value;
            vec[i] = true;

            searchSolution(i + 1);

            capacity += goods.weight;
            currentValue -= goods.value;
            vec[i] = false;
        }
        if (bound(i+1) > bestValue) {
            searchSolution(i + 1);
        }
    }

    private float bound(int i) {
        float maxValue = currentValue;
        int capacity = this.capacity;
        for (;i < goodsArrayList.size(); i++) {
            Goods goods = goodsArrayList.get(i);
            if (capacity >= goods.weight) {
                maxValue += goods.value;
                capacity -= goods.weight;
            } else {
                maxValue += (capacity * goods.weightValue);
            }
        }
        return maxValue;
    }

}
